#include <iostream>
#include <string>
#include <vector>

using namespace std;

void getNext(vector<int> & next, const string & p)
{
    int j = 1;
    int i = 0;
    next[0] = i;
    for(; j < p.size(); j++)
    {
        while (i > 0 && p[i] != p[j])
        {
            i = next[i - 1];
        }
        if(p[i] == p[j])
        {
            i++;
        }
        next[j] = i;
    }
}

class Solution 
{
public:
    int strStr(string haystack, string needle) 
    {
        if(haystack.empty() == true)
        {
            return 0;
        }
        if(needle.length() > haystack.length())
        {
            return -1;
        }
        vector<int> next(needle.length());
        getNext(next, needle);
        for(int i = 0, j = 0; i < haystack.length(); i++)
        {
            while (j > 0 && haystack[i] != needle[j])
            {
                j = next[j - 1];
            }
            if(haystack[i] == needle[j])
            {
                j++;
            }
            if (j == needle.length())
            {
                return i + 1 - j;
            }
        }
        return -1;
    }
};